class UnionFind:
    def __init__(self, n):
        self.fa = list(range(n + 1))
        self.size = [1] * (n + 1)

    def find(self, x):
        if self.fa[x] != x:
            self.fa[x] = self.find(self.fa[x])
        return self.fa[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y: return False
        if self.size[root_x] > self.size[root_y]:
            root_x, root_y = root_y, root_x
        self.fa[root_y] = root_x
        self.size[root_x] += self.size[root_y]


if __name__ == '__main__':
    uf = UnionFind(15)
    uf.union(1, 2)
    uf.union(1, 3)
    uf.union(5, 6)
    uf.union(5, 7)
    uf.union(3, 5)
    for i in range(15):
        print(uf.find(i))
    print()
